package leetcode

/*
 * @lc app=leetcode.cn id=115 lang=golang
 *
 * [115] 不同的子序列
 */

// @lc code=start
//自低而上
func numDistinct2(s string, t string) int {
	sLen, tLen := len(s), len(t)
	dp := make([][]int, sLen+1)
	for i := range dp {
		dp[i] = make([]int, tLen+1)
		dp[i][tLen] = 1
	}
	for k := 1; k < sLen+1; k++ {
		i := sLen - k
		for l := 1; l < k+1 && l < tLen+1; l++ {
			j := tLen - l
			if s[i] == t[j] {
				dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
			} else {
				dp[i][j] = dp[i+1][j]
			}
		}
	}
	return dp[0][0]
}

//自顶而下
func numDistinct(s string, t string) int {
	sLen, tLen := len(s), len(t)
	tmp := make(map[[2]int]int, sLen*tLen/2)

	var dp func(int, int) int
	dp = func(i, j int) int {
		if sLen-i < tLen-j {
			return 0
		} else if j == tLen {
			return 1
		}
		if v, ok := tmp[[2]int{i, j}]; ok {
			return v
		}
		if s[i] == t[j] {
			tmp[[2]int{i, j}] = dp(i+1, j+1) + dp(i+1, j)
		} else {
			tmp[[2]int{i, j}] = dp(i+1, j)
		}
		return tmp[[2]int{i, j}]

	}
	return dp(0, 0)
}

// @lc code=end
